#include "graph_support/TestCommonGraphFeatures.h"

#include <stdio.h>
#include <string>
#include <sstream>
#include <math.h>
#include <numeric>
#include <vector>

#include <boost/bind.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/random.hpp>
#include <boost/date_time/posix_time/posix_time.hpp>

#include "graph_support/attributes/LengthEdgeAttributes.h"
#include "graph_support/attributes/FlowEdgeAttributes.h"

#include "graph_support/impls/vector/VectorGraph.h"
#include "graph_support/impls/matrix/MatrixGraph.h"
#include "graph_support/impls/compact/CompactGraph.h"

#include "graph_support/utils/test_my_graph/BoostTestUtils.h"
#include "graph_support/utils/CollectionsInit.h"
#include "graph_support/utils/HashSupport.h"

#include "graph_support/alg/shortest_path/Dejkstra.h"
#include "graph_support/alg/flow/Dinic.h"

#include "graph_support/fakes/BusinessType.h"

using namespace GRAPH_SUPPORT_NS;
using namespace GRAPH_SUPPORT_NS::attributes;
using namespace GRAPH_SUPPORT_NS::impls;
using namespace GRAPH_SUPPORT_NS::impls::vector;
using namespace GRAPH_SUPPORT_NS::impls::matrix;
using namespace GRAPH_SUPPORT_NS::impls::compact;
using namespace GRAPH_SUPPORT_NS::utils;
using namespace GRAPH_SUPPORT_NS::alg::shortest_path;
using namespace GRAPH_SUPPORT_NS::alg::flow;

namespace
{

void fillVector( std::vector< int > & vec )
{
	for ( int i = 0; i < vec.size(); i++ )
	{
		vec[i] = i;
	}
}

}

void TestGraphSize()
{
	typedef VectorGraphTmpl< int > GraphI;
	typedef GraphI::GrVertex GrVertex;

	int n = 5;
	std::vector< GrVertex > vec( n );
	fillVector( vec );
	GraphI gr( vec );

	BOOST_CHECK_EQUAL(
			5,
			std::accumulate( gr.getVerticesBeg(), gr.getVerticesEnd(), 0,
					boost::bind( std::plus< int >(), _1, 1 ) ) );
}

void TestSmartVert2num()
{
	typedef VectorGraphTmpl< int > IntGraph;
	typedef VectorGraphTmpl<
			int,
			Length1EdgeAttributes,
			stdext::hash< int >,
			stdext::equal_to< int >,
			ResolveTableType< int, size_t, stdext::hash< int >,
				stdext::equal_to< int > >
			> SmartIntGraph;

	int n = 100 * 	1000;
	int m = 3 * 	1000000;

	std::vector< int > vertices;
	for ( int i = 0; i < n; i++ )
	{
		vertices.push_back( i );
	}

	double timeA = -1;
	double timeB = -1;

	{
	typedef IntGraph Graph;
	typedef Graph::GrVertex GrVertex;
	boost::rand48 rgen( 12345 );
	Graph gr( vertices );
		// ~~ train, no time measure
		for ( int i = 0; i < m; i++ )
		{
			int r = rgen() % n;
			GrVertex v = r;
			int vid = gr.vert2num( v );
		}
	boost::posix_time::ptime timeBeg = boost::posix_time::microsec_clock::universal_time();
	bool correct = true;
	for ( int i = 0; i < m; i++ )
	{
		int r = rgen() % n;
		GrVertex v = r;
		int vid = gr.vert2num( v );
		correct &= ( vid == r );
	}
	BOOST_CHECK( correct );
	timeA = ( boost::posix_time::microsec_clock::universal_time() -
			timeBeg ).total_milliseconds();
	}

	{
	typedef SmartIntGraph Graph;
	typedef Graph::GrVertex GrVertex;
	boost::rand48 rgen( 12345 );
	Graph gr( vertices );
	boost::posix_time::ptime timeBeg = boost::posix_time::microsec_clock::universal_time();
	bool correct = true;
	for ( int i = 0; i < m; i++ )
	{
		int r = rgen() % n;
		GrVertex v = r;
		int vid = gr.vert2num( v );
		correct &= ( vid == r );
	}
	BOOST_CHECK( correct );
	timeB = ( boost::posix_time::microsec_clock::universal_time() -
			timeBeg ).total_milliseconds();
	}

	BOOST_CHECK_GT( timeA, timeB * 1.5 );
}

void TestZEROGraphSize()
{
	typedef VectorGraphTmpl< int > GraphI;
	typedef GraphI::GrVertex GrVertex;

	std::vector< GrVertex > vec;
	GraphI grv( vec );
	BOOST_CHECK_EQUAL(
			0,
			std::accumulate( grv.getVerticesBeg(), grv.getVerticesEnd(), 0,
					boost::bind( std::plus< int >(), _1, 1 ) ) );
	VectorGraphTmpl< int > grm( vec );
	BOOST_CHECK_EQUAL(
			0,
			std::accumulate( grm.getVerticesBeg(), grm.getVerticesEnd(), 0,
					boost::bind( std::plus< int >(), _1, 1 ) ) );
}

void TestPureNegVertices()
{
	typedef VectorGraphTmpl< int > GraphI;
	typedef GraphI::GrVertex GrVertex;

	std::vector< GrVertex > vec;
	for ( int i = -10; i < -5; vec.push_back( i++ ) );
	GraphI grv( vec );
	BOOST_CHECK_EQUAL(
			5,
			std::accumulate( grv.getVerticesBeg(), grv.getVerticesEnd(), 0,
					boost::bind( std::plus< int >(), _1, 1 ) ) );
	GraphI grm( vec );
	BOOST_CHECK_EQUAL(
			5,
			std::accumulate( grm.getVerticesBeg(), grm.getVerticesEnd(), 0,
					boost::bind( std::plus< int >(), _1, 1 ) ) );
}

void TestMixedIntVerticesGraphGraph()
{
	typedef VectorGraphTmpl< int > GraphI;
	typedef GraphI::GrVertex GrVertex;
	typedef GraphI::EdgeIterator EdgeIterator;

	std::vector< GrVertex > vertices =
			arr2vector< int >( ( const int[] ) { -1, -2, -3, 1, 2, 3 } );
	BOOST_CHECK_EQUAL( 6, vertices.size() );

	GraphI gr( vertices );
	BOOST_CHECK_EQUAL( 3, gr.vert2num( 1 ) );
	BOOST_CHECK_EQUAL( 0, gr.vert2num( -1 ) );
	BOOST_CHECK_EQUAL( 2, gr.vert2num( -3 ) );
	BOOST_CHECK_EQUAL( ( size_t ) Graph::NOT_A_VERTEX_ID, gr.vert2num( -4 ) );
	BOOST_CHECK_EQUAL( ( size_t ) Graph::NOT_A_VERTEX_ID, gr.vert2num( 4 ) );

	BOOST_CHECK( ! utils::findEdge( gr, 1, 2 ) );
	BOOST_CHECK( ! utils::findEdge( gr, -1, 2 ) );

	gr.addEdge( -1, 2 );
	BOOST_CHECK( ! utils::findEdge( gr, 1, 2 ) );
	BOOST_CHECK( utils::findEdge( gr, -1, 2 ) );

}

void TestIntVertices()
{
	typedef VectorGraphTmpl< int > GraphI;
	typedef GraphI::GrVertex GrVertex;
	typedef GraphI::EdgeIterator EdgeIterator;

	std::vector< GrVertex > vec10( 10 );
	fillVector( vec10 );
	GraphI gr( vec10.begin(), vec10.end() );

	BOOST_CHECK( ! utils::findEdge( gr, 3, 7 ) );
	gr.addEdge( 3, 7 );
	BOOST_CHECK( utils::findEdge( gr, 3, 7 ) );

	gr.addEdge( 3, 8 );
	gr.addEdge( 3, 6 );

	std::stringstream tmp;
	for ( EdgeIterator it = gr.getEdgsBeg( 3 ); it != gr.getEdgsEnd( 3 ); ++it )
	{
		tmp << " " << ( * it )->end();
	}
	std::string outEdges = tmp.str();
	BOOST_CHECK_EQUAL( std::string( " 7 8 6" ), outEdges );
}

void TestCharVertices()
{
	typedef VectorGraphTmpl< const char * > GraphCh;
	typedef GraphCh::GrVertex GrVertex;

	std::vector< GrVertex > names =
			arr2vector< GrVertex >( ( GrVertex const [] ) { "abc", "def", "qwe" } );
	BOOST_CHECK_EQUAL( 3, names.size() );

	GraphCh gr( names );

	BOOST_CHECK( ! utils::findEdge( gr, "abc", "def" ) );
	gr.addEdge( "abc", "def" );
	BOOST_CHECK( utils::findEdge( gr, "abc", "def" ) );
}

// TODO: move 2 vector graph since only vg implementation uses this wrap
void TestCastWrap2Vert()
{
	typedef VertexWrap< const char *, Length1EdgeAttributes > GrVertexWrap;

	GrVertexWrap wrA( "A" );
	GrVertexWrap wrB( "B" );
	std::vector< GrVertexWrap > wraps;
	wraps.push_back( wrA );
	wraps.push_back( wrB );

	VectorGraphTmpl< const char * >::GrEdge edge( 0, 1, wraps );
	BOOST_CHECK_EQUAL( std::string( "A" ), edge.beg() );
	BOOST_CHECK_EQUAL( std::string( "B" ), edge.end() );
}

void TestSTDStringVertices()
{
	typedef VectorGraphTmpl< const char *, LengthEdgeAttributesTmpl< double > > GraphCh;
	typedef GraphCh::GrVertex GrVertex;
	typedef GraphCh::GrEdge::EdgeAttributes EdgeAttributes;

	std::vector< GrVertex > names =
			arr2vector< GrVertex >( ( GrVertex const [] )
					{ "123, 234", "333, 654", "765, 234" } );
	BOOST_CHECK_EQUAL( 3, names.size() );

	GraphCh gr( names );

	gr.addEdge( "123, 234", "333, 654", EdgeAttributes( hypot( 123 - 333, 234 - 654 ) ) );
	gr.addEdge( "333, 654", "765, 234", EdgeAttributes( hypot( 333 - 765, 654 - 234 ) ) );
	gr.addEdge( "765, 234", "123, 234", EdgeAttributes( hypot( 765 - 123, 234 - 234 ) ) );

	BOOST_CHECK_GT( ( * gr.getEdgsBeg( "123, 234" ) )->getAttributes().getLength(), floor( hypot( 123 - 333, 234 - 654 ) ) );
	BOOST_CHECK_LT( ( * gr.getEdgsBeg( "123, 234" ) )->getAttributes().getLength(), ceil( hypot( 123 - 333, 234 - 654 ) ) );
}

void TestForEachOutcomeEdge()
{
	typedef VectorGraphTmpl< int > Graph;
	typedef Graph::GrVertex GrVertex;
	typedef Graph::GrEdge GrEdge;
	typedef Graph::GrEdgePtr GrEdgePtr;

	Graph gr( arr2vector< int >( ( const int [] ) { -1, 0, 1, 2, 3, 4 } ) );
	gr.addEdge( 0, 1 );
	gr.addEdge( 0, 3 );
	gr.addEdge( 0, 4 );
	gr.addEdge( 3, 4 );

	std::stringstream buf;
	std::for_each( gr.getEdgsBeg( 0 ), gr.getEdgsEnd( 0 ),
			boost::bind( & shlOperator< std::stringstream, GrVertex >, boost::ref( buf ), boost::bind( & GrEdge::end, _1 ) ) );
	BOOST_CHECK_EQUAL( std::string( "134" ), buf.str() );
	gr.forEachOutEdge( 0,
			boost::bind( & shlOperator< std::stringstream, GrVertex >, boost::ref( buf ), boost::bind( & GrEdge::end, _1 ) ) );
	BOOST_CHECK_EQUAL( std::string( "134134" ), buf.str() );
	gr.forEachOutEdge( 3,
			boost::bind( & shlOperator< std::stringstream, GrVertex >, boost::ref( buf ), boost::bind( & GrEdge::end, _1 ) ) );
	BOOST_CHECK_EQUAL( std::string( "1341344" ), buf.str() );
	gr.forEachOutEdgeId( ( size_t ) 1,
			boost::bind( & shlOperator< std::stringstream, GrVertex >, boost::ref( buf ), boost::bind( & GrEdge::endId, _1 ) ) );
	BOOST_CHECK_EQUAL( std::string( "1341344245" ), buf.str() );
}

void TestBidirGraph()
{
	typedef VectorGraphTmpl< int > GraphI;
	typedef GraphI::GrVertex GrVertex;

	int n = 10;
	std::vector< GrVertex > vertices( n );
	fillVector( vertices );

	{
	GraphI gr( vertices );
	BOOST_CHECK( ! utils::findEdge( gr, 1, 2 ) );
	BOOST_CHECK( ! utils::findEdge( gr, 2, 1 ) );

	gr.addEdge( 1, 2 );
	BOOST_CHECK( utils::findEdge( gr, 1, 2 ) );
	BOOST_CHECK( ! utils::findEdge( gr, 2, 1 ) );
	}

	{
	GraphI gr( vertices, true );
	BOOST_CHECK( ! utils::findEdge( gr, 1, 2 ) );
	BOOST_CHECK( ! utils::findEdge( gr, 2, 1 ) );

	gr.addEdge( 1, 2 );
	BOOST_CHECK( utils::findEdge( gr, 1, 2 ) );
	BOOST_CHECK( utils::findEdge( gr, 2, 1 ) );
	}
}

typedef VectorGraphTmpl<
		test_gs_fakes::BusinessType *,
		Length1EdgeAttributes,
		Hash4AbstractPointer< test_gs_fakes::BusinessType >
		> BsnsGraph;
typedef std::vector<
		test_gs_fakes::BusinessType
		> BsnsObjsColl;
typedef std::vector<
		test_gs_fakes::BusinessType *
		> BsnsVerticesColl;
typedef VectorGraphTmpl<
		test_gs_fakes::BusinessType,
		Length1EdgeAttributes,
		test_gs_fakes::BsnsHashMapSupport,
		test_gs_fakes::BsnsHashMapSupport
		> SevereBsnsGraph;

void TestBusinessGraph()
{
	using namespace test_gs_fakes;

	const BusinessType bobjsbuf[] = {
			BusinessType( "hello - 0" ),
			BusinessType( "hello - 1" ),
			BusinessType( "hello - 2" ),
		};
	BsnsObjsColl bobjs =
			arr2vector< BusinessType >( bobjsbuf );
	BOOST_CHECK_EQUAL( 3, bobjs.size() );

	BsnsVerticesColl bverts( bobjs.size() );
	for ( int i = 0; i < bobjs.size(); i++ )
	{
		bverts[i] = & bobjs[i];
	}

	BsnsGraph graph( bverts );
	BOOST_CHECK( ! findEdge( graph, bverts[0], bverts[1] ) );

	graph.addEdge( bverts[0], bverts[1] );
	BOOST_CHECK( findEdge( graph, bverts[0], bverts[1] ) );

	graph.addEdge( bverts[0], bverts[2] );
	graph.addEdge( bverts[1], bverts[2] );
	BOOST_CHECK( findEdge( graph, bverts[0], bverts[2] ) );
	BOOST_CHECK( findEdge( graph, bverts[1], bverts[2] ) );

	// severe

	SevereBsnsGraph cgr( bobjs );
	BOOST_CHECK( ! utils::findEdge( cgr, BusinessType( "hello - 0" ), BusinessType( "hello - 1" ) ) );
	cgr.addEdge( BusinessType( "hello - 0" ), BusinessType( "hello - 1" ) );
	BOOST_CHECK( utils::findEdge( cgr, BusinessType( "hello - 0" ), BusinessType( "hello - 1" ) ) );
}

class BusinessFlow
{
public:
	BusinessFlow( int majorFlow, int minorFlow )
		: majorFlow( majorFlow )
		, minorFlow( minorFlow )
	{
	}
	BusinessFlow( int intFlow )
	{
		* this = intFlow;
	}
	const BusinessFlow & operator = ( const int & intVal )
	{
		majorFlow = intVal;
		minorFlow = 0;
		return * this;
	}

public:
	int getMajorFlow()
	{
		return majorFlow;
	}
	int getMinorFlow()
	{
		return minorFlow;
	}

public:
	bool operator > ( const BusinessFlow & that ) const
	{
		return compare( that ) > 0;
	}
	bool operator < ( const BusinessFlow & that ) const
	{
		return compare( that ) < 0;
	}
	bool operator >= ( const BusinessFlow & that ) const
	{
		return compare( that ) >= 0;
	}
	bool operator <= ( const BusinessFlow & that ) const
	{
		return compare( that ) <= 0;
	}
	bool operator == ( const BusinessFlow & that ) const
	{
		return compare( that ) == 0;
	}
	BusinessFlow operator - ( const BusinessFlow & that ) const
	{
		return BusinessFlow( majorFlow - that.majorFlow, minorFlow - that.minorFlow );
	}
	BusinessFlow operator + ( const BusinessFlow & that ) const
	{
		return BusinessFlow( majorFlow + that.majorFlow, minorFlow + that.minorFlow );
	}
	const BusinessFlow & operator += ( const BusinessFlow & that )
	{
		majorFlow += that.majorFlow;
		minorFlow += that.minorFlow;
		return *this;
	}
	const BusinessFlow & operator -= ( const BusinessFlow & that )
	{
		majorFlow -= that.majorFlow;
		minorFlow -= that.minorFlow;
		return *this;
	}

public:
	operator std::string () const
	{
		char buf[100];
		int wsz = sprintf( buf, "BusinessFlow: M=%d, m=%d", majorFlow, minorFlow );
		assert( wsz > 0 );
		return std::string( buf );
	}

private:
	int compare( const BusinessFlow & that ) const
	{
		if ( majorFlow > that.majorFlow )
		{
			return 1;
		}
		if ( majorFlow < that.majorFlow )
		{
			return -1;
		}
		if ( minorFlow > that.minorFlow )
		{
			return 1;
		}
		if ( minorFlow < that.minorFlow )
		{
			return -1;
		}
		return 0;
	}

private:
	int majorFlow;
	int minorFlow;
};
	/**
	 * makes BusinessFlow OStreamable
	 */
	std::ostream & operator << ( std::ostream & ostr, const BusinessFlow & bf )
	{
		ostr << ( ( std::string ) bf );
		return ostr;
	}

typedef FlowEdgeAttributesTmpl< BusinessFlow > BusinessEdgeAttrs;
typedef VectorGraphTmpl<
		test_gs_fakes::BusinessType,
		BusinessEdgeAttrs,
		test_gs_fakes::BsnsHashMapSupport,
		test_gs_fakes::BsnsHashMapSupport
		> BsnsFlowGraph;
typedef Dinic< BsnsFlowGraph > BsnsFlowDinic;

void TestBusinessGraphDinic()
{
	using namespace test_gs_fakes;

	const BusinessType bobjsbuf[] = {
			BusinessType( "bt-0" ),
			BusinessType( "bt-1" ),
			BusinessType( "bt-2" ),
		};
	BsnsObjsColl bobjs = arr2vector< BusinessType >( bobjsbuf );
	BusinessType src = BusinessType( "bt-0" );
	BusinessType & dest = bobjs[1]; // test &

	BsnsFlowGraph graph( bobjs, true );

	graph.addEdge( src, dest, BusinessEdgeAttrs( BusinessFlow( 123, 456 ) ) );
	BOOST_CHECK( findEdge( graph, src, dest ) );
	BOOST_CHECK_EQUAL( 123, findEdge( graph, src, dest ).get()->getAttributes().getCapacity().getMajorFlow() );
	BOOST_CHECK( findEdge( graph, dest, src ) );
	if ( findEdge( graph, dest, src ) )
	BOOST_CHECK_EQUAL( 0, findEdge( graph, dest, src ).get()->getAttributes().getCapacity().getMajorFlow() );

	graph.addEdge( src, BusinessType( "bt-2" ), BusinessEdgeAttrs( BusinessFlow( 32, 543 ) ) );
	graph.addEdge( BusinessType( "bt-2" ), dest, BusinessEdgeAttrs( BusinessFlow( 50, 500 ) ) );

	BsnsFlowDinic dinic( graph );
	dinic( src, dest );
	BusinessFlow flow = dinic.getTotalFlow();
	BOOST_CHECK( BusinessFlow( 155, 999 ) == flow );
	BOOST_CHECK_EQUAL( ( std::string ) BusinessFlow( 155, 999 ), ( std::string ) flow );

	BOOST_CHECK_EQUAL(
			( std::string )
			( dinic.getFlow( BusinessType( "bt-0" ), BusinessType( "bt-1" ) ) +
			  dinic.getFlow( BusinessType( "bt-0" ), BusinessType( "bt-2" ) ) ),
			( std::string ) dinic.getTotalFlow()
			);
	BOOST_CHECK_EQUAL(
			( std::string ) dinic.getFlow( BusinessType( "bt-0" ), BusinessType( "bt-2" ) ),
			( std::string ) dinic.getFlow( BusinessType( "bt-2" ), BusinessType( "bt-1" ) )
			);
}

void TestMatrixGraph()
{
	typedef MatrixGraphTmpl<
			std::string,
			Length1EdgeAttributes,
			Hash4StdString
			> StrMatrixGraph;
	typedef StrMatrixGraph::GrEdgePtr SMGrEdgePtr;
	typedef StrMatrixGraph::EdgeIterator SMGEdgeIterator;
	BOOST_CHECK_EQUAL( sizeof( std::string ), sizeof( StrMatrixGraph::GrVertex ) );

	const std::string verticesbuf[] = {
			"v0", "v1", "v2", "v3",
	};
	std::vector< std::string > vertices = arr2vector< std::string >( verticesbuf );
	BOOST_CHECK_EQUAL( 4, vertices.size() );

	// vertices count
	{
	StrMatrixGraph graph( vertices.begin(), vertices.end() );
	BOOST_CHECK_EQUAL( 4, graph.getVertexCount() );
	}
	StrMatrixGraph graph( vertices );
	BOOST_CHECK_EQUAL( 4, graph.getVertexCount() );

	// iterate vertices
	char printBuf[1000];
	char * printPtr = printBuf;
	printPtr[0] = '\0';
	for ( StrMatrixGraph::VertexIterator it = graph.getVerticesBeg(); it != graph.getVerticesEnd(); ++it )
	{
		int l = sprintf( printPtr, "%s; ", it->c_str() );
		BOOST_CHECK_GT( l, 0 );
		printPtr += l;
	}
	BOOST_CHECK_EQUAL( std::string( "v0; v1; v2; v3; " ), std::string( printBuf ) );

	// vert 2 num
	BOOST_CHECK_EQUAL( 2, graph.vert2num( "v2" ) );
	BOOST_CHECK_EQUAL( std::string( "v3" ), graph.num2vert( 3 ) );

	// edges
	BOOST_CHECK( ! findEdge( graph, "v2", "v3" ) );
	graph.addEdge( "v2", "v3" );
	BOOST_CHECK( findEdge( graph, "v2", "v3" ) );
	BOOST_CHECK( ! findEdge( graph, "v3", "v2" ) );

	// bidirected
	StrMatrixGraph graph1( vertices, true );
	graph1.addEdge( "v2", "v0" );
	BOOST_CHECK( findEdge( graph1, "v2", "v0" ) );
	BOOST_CHECK( findEdge( graph1, "v0", "v2" ) );

	// iterate edges
	printPtr = printBuf;
	printPtr[0] = '\0';
	for ( SMGEdgeIterator it = graph1.getEdgsBeg( "v2" ); it != graph1.getEdgsEnd( "v2" ); ++it )
	{
		SMGrEdgePtr edgePtr = * it;
		int l = sprintf( printPtr, "%s -> %s; ", edgePtr->beg().c_str(), edgePtr->end().c_str() );
		BOOST_CHECK_GT( l, 0 );
		printPtr += l;
	}
	BOOST_CHECK_EQUAL( std::string( "v2 -> v0; " ), std::string( printBuf ) );
	graph1.addEdge( "v2", "v2" );
	printPtr = printBuf;
	printPtr[0] = '\0';
	for ( SMGEdgeIterator it = graph1.getEdgsBeg( "v2" ); it != graph1.getEdgsEnd( "v2" ); ++it )
	{
		SMGrEdgePtr edgePtr = * it;
		int l = sprintf( printPtr, "%s -> %s; ", edgePtr->beg().c_str(), edgePtr->end().c_str() );
		BOOST_CHECK_GT( l, 0 );
		printPtr += l;
	}
	BOOST_CHECK_EQUAL( std::string( "v2 -> v0; v2 -> v2; " ), std::string( printBuf ) );

	//Dejkstra
	graph1.addEdge( "v2", "v0" );
	graph1.addEdge( "v2", "v3" );
	Dejkstra< StrMatrixGraph > dejkstra( graph1 );
	dejkstra( "v2" );
	BOOST_CHECK_EQUAL( 1, dejkstra.getDistance( "v0" ) );
	BOOST_CHECK_EQUAL( 1, dejkstra.getDistance( "v3" ) );
	BOOST_CHECK_EQUAL( 1 << 30, dejkstra.getDistance( "v1" ) );
	graph1.addEdge( "v3", "v1" );
	dejkstra( "v2" );
	BOOST_CHECK_EQUAL( 2, dejkstra.getDistance( "v1" ) );

	//Dinic
	typedef MatrixGraphTmpl< int, BusinessEdgeAttrs > MtrxFlGraph;
	std::vector< int > mfv = arr2vector< int >( ( const int[] ) { 10, 11, 12 } );
	BOOST_CHECK_EQUAL( 3, mfv.size() );
	MtrxFlGraph mfg( mfv, true );
	mfg.addEdge( 10, 11, BusinessEdgeAttrs( BusinessFlow( 10, 20 ) ) );
	Dinic< MtrxFlGraph > mdin( mfg );
	mdin( 10, 11 );
	BOOST_CHECK_EQUAL( std::string( "BusinessFlow: M=10, m=20" ), ( std::string ) mdin.getTotalFlow() );
	BOOST_CHECK_EQUAL( std::string( "BusinessFlow: M=10, m=20" ), ( std::string ) mdin.getFlow( 10, 11 ) );
	BOOST_CHECK_EQUAL( std::string( "BusinessFlow: M=-10, m=-20" ), ( std::string ) mdin.getFlow( 11, 10 ) );
	mfg.addEdge( 10, 12, BusinessEdgeAttrs( BusinessFlow( 30, 40 ) ) );
	mfg.addEdge( 12, 11, BusinessEdgeAttrs( BusinessFlow( 40, 30 ) ) );
	mdin( 10, 11 );
	BOOST_CHECK_EQUAL( std::string( "BusinessFlow: M=40, m=60" ), ( std::string ) mdin.getTotalFlow() );
	BOOST_CHECK_EQUAL( std::string( "BusinessFlow: M=-30, m=-40" ), ( std::string ) mdin.getFlow( 12, 10 ) );
}

void TestEdgeOverflowForCompactGraph()
{
	typedef CompactGraphTmpl< const char * > Graph;

	Graph gr( arr2vector< const char * >( ( const char * const [] ) { "A", "B", "C", "D", "E", "F", "G", "H" } ) );
	int n = gr.getVertexCount();
	int m = n * n * n * 3;

	boost::rand48 randomGenerator( 123987 );

	for ( int i = 0; i < m; i++ )
	{
		size_t avid = randomGenerator() % n;
		size_t bvid = randomGenerator() % n;

		Graph::GrVertex aname = gr.num2vert( avid );
		Graph::GrVertex bname = gr.num2vert( bvid );

		gr.addEdge( aname, bname );

		BOOST_CHECK( utils::findEdge( gr, aname, bname ) );
	}

	int counter = 0;
	for ( Graph::VertexIterator vit = gr.getVerticesBeg(); vit != gr.getVerticesEnd(); ++ vit )
	{
		for ( Graph::EdgeIterator eit = gr.getEdgsBeg( * vit ); eit != gr.getEdgsEnd( * vit ); ++ eit )
		{
			counter++;
		}
	}
	BOOST_CHECK_EQUAL( m, counter );
}

void TestEdgeOverflowForCompactGraph_FlowNet()
{
	typedef CompactGraphTmpl< const char *, FlowEdgeAttributesTmpl< double > > FlowNet;

	FlowNet gr( arr2vector< const char * >( ( const char * const [] ) { "A", "B", "C", "D", "E", "F", "G", "H" } ), true );
	int n = gr.getVertexCount();
	int m = n * n * n * 3;

	boost::rand48 randomGenerator( 123987 );

	for ( int i = 0; i < m; i++ )
	{
		size_t avid = randomGenerator() % n;
		size_t bvid = randomGenerator() % n;
		FlowNet::GrVertex aname = gr.num2vert( avid );
		FlowNet::GrVertex bname = gr.num2vert( bvid );

		gr.addEdge( aname, bname,
				( ( double ) ( randomGenerator() % 1000000 ) ) / 1000.0 );
		BOOST_CHECK( utils::findEdge( gr, aname, bname ) );
	}


	Dinic< FlowNet > dinic( gr );
	dinic( "A", "B" );
	BOOST_CHECK_CLOSE( 78374.605, dinic.getTotalFlow(), 1e-5 );
}
